{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #无重复字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLongestSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无重复字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> ，请你找出其中不含有重复字符的&nbsp;<strong>最长连续子字符串&nbsp;</strong>的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;abcabcbb&quot;\n",
    "<strong>输出: </strong>3 \n",
    "<strong>解释:</strong> 因为无重复字符的最长子字符串是 <code>&quot;abc&quot;，所以其</code>长度为 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;bbbbb&quot;\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>因为无重复字符的最长子字符串是 <code>&quot;b&quot;</code>，所以其长度为 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;pwwkew&quot;\n",
    "<strong>输出: </strong>3\n",
    "<strong>解释: </strong>因为无重复字符的最长子串是&nbsp;<code>&quot;wke&quot;</code>，所以其长度为 3。\n",
    "&nbsp;    请注意，你的答案必须是 <strong>子串 </strong>的长度，<code>&quot;pwke&quot;</code>&nbsp;是一个<em>子序列，</em>不是子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = &quot;&quot;\n",
    "<strong>输出: </strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;由英文字母、数字、符号和空格组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 3&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/\">https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [wtcaE1](https://leetcode.cn/problems/wtcaE1/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [wtcaE1](https://leetcode.cn/problems/wtcaE1/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return len(s)\n",
    "        max_len = 1\n",
    "        i = j = 0\n",
    "        while j < len(s)-1:\n",
    "            j += 1            \n",
    "            if s[j] not in s[i:j]:\n",
    "                max_len = max(max_len, j-i+1)\n",
    "            else:\n",
    "                while s[j] in s[i:j]:\n",
    "                    i += 1\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        动态规划\n",
    "        set记录\n",
    "        dp[i] 以i结尾的字符串的最长子串长度\n",
    "        dp[i] = dp[i-1] + 1  i - set[i] > dp[i-1] \n",
    "        dp[i] = i - set[i]  i - set[i] < dp[i-1]\n",
    "        dp[i] = dp[i - 1] + 1 set[i]不存在\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "            \n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = 1\n",
    "        pre_index = {}\n",
    "        \n",
    "\n",
    "        for i in range(0, n):\n",
    "            ch  = s[i]\n",
    "            if ch not in pre_index:\n",
    "                pre_index[ch] = i\n",
    "                if i == 0:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                ch_pre_index = pre_index[ch]\n",
    "                l = i - ch_pre_index\n",
    "                if l > dp[i - 1]:\n",
    "                    dp[i] = dp[i - 1] + 1\n",
    "                else:\n",
    "                    dp[i] = l\n",
    "                pre_index[ch] = i\n",
    "        \n",
    "        print(dp)\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return len(s)\n",
    "        # DP[N] 以N为结尾的最长子串长度\n",
    "        dp = [1] * len(s)\n",
    "        # dp_test = self.findBackward(s, 5, 3)\n",
    "        for i in range(1, len(s)):\n",
    "            dp[i] = self.findBackward(s, i, dp[i-1])\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "    def findBackward(self, s: str, index: int, sub_len: int):\n",
    "        for i in range(1, sub_len+1):\n",
    "            if s[index - i] in s[index - i + 1:index+1]:\n",
    "                return i\n",
    "        return sub_len + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        if not len(s):\n",
    "            return 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        def add(dic, item):\n",
    "            if item not in dic:\n",
    "                dic[item] = 1\n",
    "            else:\n",
    "                dic[item] += 1\n",
    "            \n",
    "        def drop(dic, item):\n",
    "            if dic[item] >= 2:\n",
    "                dic[item] -= 1\n",
    "            else:\n",
    "                dic.drop(item)\n",
    "        \n",
    "        dic = dict()\n",
    "        s_length = len(s)\n",
    "        ret = 0\n",
    "        dic[s[0]] = 1\n",
    "        arr_ret = [ret]\n",
    "        left, right = 0, 1\n",
    "        cnt = 1\n",
    "        for left, l_val in enumerate(s[:-1]):\n",
    "            if left > 0:\n",
    "                dic.pop(s[left-1])\n",
    "                cnt -= 1\n",
    "            while right < s_length:\n",
    "                r_val = s[right]\n",
    "                if r_val not in dic:\n",
    "                    dic[r_val] = 1\n",
    "                    cnt += 1\n",
    "                    right += 1\n",
    "                else:\n",
    "                    arr_ret.append(cnt)\n",
    "                    ret = max(ret, cnt)\n",
    "                    break\n",
    "            ret = max(ret, cnt)\n",
    "        print(arr_ret, ret)\n",
    "        return ret\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        size = len(s)\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        dp = [0] * size\n",
    "        dp[0] = 1\n",
    "\n",
    "        chSet = set()\n",
    "        chSet.add(s[0])\n",
    "        for i in range(1, size):\n",
    "            if s[i] not in chSet:\n",
    "                chSet.add(s[i])\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                index = 0\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if s[i] == s[j]:\n",
    "                        index = j\n",
    "                        break\n",
    "                dp[i] = i - index \n",
    "                chSet = set()\n",
    "                for k in range(index+1, i+1):\n",
    "                    chSet.add(s[k])\n",
    "                #print(i,dp, chSet)\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "        absqwertyba"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        le = len(s)\n",
    "        dp = [0] * (le + 1)\n",
    "        max_len = 0\n",
    "        for i in range(1, le + 1):\n",
    "            if i == 1:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                for j in range(i - dp[i-1], i)[::-1]:\n",
    "                    if s[i - 1] == s[j - 1]:\n",
    "                        dp[i] = i - j\n",
    "                        break\n",
    "                if dp[i] == 0:\n",
    "                    dp[i] = dp[i - 1] + 1\n",
    "            if max_len < dp[i]:\n",
    "                max_len = dp[i]\n",
    "        print(dp)\n",
    "        return max_len\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        result = 1\n",
    "        contain = [1 for i in range(len(s))]\n",
    "        not_contain = [1 for i in range(len(s))]\n",
    "\n",
    "        if s == \"\":\n",
    "            return 0\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] not in s[i-contain[i-1]:i]:\n",
    "                contain[i] = contain[i-1] + 1\n",
    "            else:\n",
    "                contain[i] = self.find(s, i-1, contain[i-1], s[i])\n",
    "            not_contain[i] = max(contain[i-1], not_contain[i-1])\n",
    "        \n",
    "        return max(max(contain), max(not_contain))\n",
    "\n",
    "    def find(self, s, id, num, target):\n",
    "        for i in range(id, id-num, -1):\n",
    "            if s[i] == target:\n",
    "                return id - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        s_dict = {}\n",
    "        res = 0\n",
    "        i = -1\n",
    "        for j in range(len(s)):\n",
    "            if s[j] in s_dict:\n",
    "                i = max(s_dict[s[j]], i)\n",
    "            s_dict[s[j]] = j\n",
    "            res = max(res, j - i)\n",
    "        return res\n",
    "\n",
    "        # if not s:\n",
    "        #     return 0\n",
    "        # start = 0  # 滑动窗口的起始位置\n",
    "        # max_len = 0  # 最长子串的长度\n",
    "        # char_index_map = {}  # 用于存储字符和它们的最近出现位置\n",
    "        # max_substring = \"\"  # 最长子串\n",
    "        # for end in range(len(s)):\n",
    "        #     if s[end] in char_index_map and char_index_map[s[end]] >= start:\n",
    "        #         start = char_index_map[s[end]] + 1\n",
    "        #     char_index_map[s[end]] = end\n",
    "        #     if (end - start + 1) > max_len:\n",
    "        #         max_len = end - start + 1\n",
    "        #         max_substring = s[start:end+1]\n",
    "        # return len(max_substring)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        hmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right, c in enumerate(s):\n",
    "            if c in hmap:\n",
    "                left = max(left, hmap[c] + 1)\n",
    "            ans = max(ans, right - left + 1)\n",
    "            hmap[c] = right\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        i=-1\n",
    "        length=len(s)\n",
    "        max_length = -1\n",
    "        temp_dict = {}\n",
    "        for j in range(length):\n",
    "            cur_alpha = s[j]\n",
    "            if cur_alpha not in temp_dict:\n",
    "                max_length = max(max_length,j-i)\n",
    "            else:\n",
    "                i = max(i,temp_dict[cur_alpha])\n",
    "                max_length = max(max_length,j-i)\n",
    "            temp_dict[cur_alpha]= j\n",
    "        return max(max_length,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if len(s) <= 1: return len(s)\n",
    "\n",
    "        char_map, left, ans = dict(), -1, 0\n",
    "        for i, char in enumerate(s):\n",
    "            if char in char_map:\n",
    "                left = max(left, char_map[char])\n",
    "            char_map[char] = i\n",
    "            ans = max(ans, i - left)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        harsh = dict()\n",
    "        res = 0\n",
    "        start = -1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in harsh:\n",
    "                start = max(start,harsh[s[i]])\n",
    "            harsh[s[i]] = i\n",
    "            \n",
    "            res = max(res,i-start)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        result = 0\n",
    "        j = 0\n",
    "        a = dict()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in a:\n",
    "                j = max(a[s[i]] + 1, j)\n",
    "            a[s[i]] = i\n",
    "            result = max(result, i - j + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        calc = {}\n",
    "        left = 0\n",
    "        ret = 0\n",
    "        for i, j in enumerate(s):\n",
    "            if j in calc:\n",
    "                # 如果重复的数字出现在l之前忽略，否则了跳到该值的下一个位置\n",
    "                left = max(left, calc[j] + 1)\n",
    "            calc[j] = i\n",
    "            ret = max(ret, i - left + 1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        map = {}\n",
    "        index = 0\n",
    "        left = 0\n",
    "        max = 0\n",
    "        for ch in s:\n",
    "            if map.__contains__(ch):\n",
    "                if map[ch] + 1 > left:\n",
    "                    left = map[ch] + 1\n",
    "            if index - left + 1 > max:\n",
    "                max = index - left + 1\n",
    "            map[ch] = index\n",
    "            index = index + 1\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        max_leng = 0\n",
    "        start = 0\n",
    "        leng = 0\n",
    "        occ = set()\n",
    "        for i, c in enumerate(s):\n",
    "            if c in occ:\n",
    "                while s[start] != c:\n",
    "                    occ.remove(s[start])\n",
    "                    start += 1\n",
    "                start += 1\n",
    "            else:\n",
    "                occ.add(c)\n",
    "                leng = i - start + 1\n",
    "                max_leng = max(max_leng, leng)\n",
    "        return max_leng"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str):\n",
    "        if not s:\n",
    "            return 0\n",
    "        res = 0\n",
    "        d = set()\n",
    "        i, j = 0, 0\n",
    "        while j < len(s):\n",
    "            if not d or s[j] not in d:\n",
    "                d.add(s[j])\n",
    "            else:\n",
    "                while d and s[j] in d:\n",
    "                    d.remove(s[i])\n",
    "                    i += 1\n",
    "                d.add(s[j])\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        i = -1 # 起始的index\n",
    "        res = 0 # 记录最长不重复字段\n",
    "        dic = {} # 更新字符的最大索引\n",
    "        for j in range(len(s)):\n",
    "            if s[j] in dic:\n",
    "                i = max(dic[s[j]],i) # 不重复出现字符的左边界\n",
    "            dic[s[j]] = j # 更新字符的最大index\n",
    "            res = max(res,j-i) # 更新不重复的字串数\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left, right = 0, 0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        record = set()\n",
    "        while right < n:\n",
    "            while right < n and s[right] not in record:\n",
    "                record.add(s[right])\n",
    "                right += 1\n",
    "\n",
    "            ans = max(ans, right - left)\n",
    "            while left < n and right < n and s[right] in record:\n",
    "                record.remove(s[left])\n",
    "                left += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        result = j = 0\n",
    "        a = dict()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in a:\n",
    "                j = max(a[s[i]] + 1, j)\n",
    "            a[s[i]] = i\n",
    "            result = max(result, i - j + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        #哈希集合用于记录每个字否有没有出现过\n",
    "        occ = set()\n",
    "        n = len(s)\n",
    "        right, ans = -1, 0\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                occ.remove(s[i - 1])\n",
    "            while right + 1 < n and s[right + 1] not in occ:\n",
    "                occ.add(s[right + 1])\n",
    "                right += 1\n",
    "            ans = max(ans, right - i + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        res = 1\n",
    "        while(j < len(s)):\n",
    "            while(s[j] in s[i:j]):\n",
    "                i += 1        \n",
    "            j += 1\n",
    "            res = max(res, j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "#         res = 0\n",
    "#         l = r = 0\n",
    "#         window = []\n",
    "#         while r < len(s):\n",
    "#             while s[r] in window and l <= r:\n",
    "#                 window.pop(0)\n",
    "#                 l += 1\n",
    "#             window.append(s[r])\n",
    "#             res = max(res, r - l + 1)\n",
    "#             r += 1\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        res = 0\n",
    "        l = r = 0\n",
    "        cache = {}\n",
    "        for index, c in enumerate(s):\n",
    "            if c in cache:\n",
    "                l = max(l, cache[c] + 1)\n",
    "            cache[c] = index\n",
    "            res = max(res, index - l + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        max_len = 0\n",
    "        if len(s)<=1:\n",
    "            return len(s)\n",
    "        while right<len(s):\n",
    "            if s[right] not in s[left:right]:\n",
    "                max_len = max(max_len,len(s[left:right])+1)\n",
    "            else:\n",
    "                left = s[left:right].index(s[right])+left+1\n",
    "            right = right+1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        record = set()\n",
    "        max_length = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in record:\n",
    "                record.add(s[i])\n",
    "                max_length = max(max_length, len(record))\n",
    "            else:\n",
    "                while s[left]!=s[i]:\n",
    "                    if s[left] in record:\n",
    "                        record.remove(s[left])\n",
    "                    left += 1\n",
    "                left += 1\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l = r = 0\n",
    "        res = \"\"\n",
    "        tmp = 0\n",
    "        while r < n:\n",
    "            if s[r] not in res:\n",
    "                r += 1\n",
    "                res = s[l:r]\n",
    "            else:\n",
    "                l += 1 \n",
    "                res = s[l:r]\n",
    "            ans = r - l\n",
    "            if tmp < ans:\n",
    "                tmp = ans\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        if l<=1:\n",
    "            return l\n",
    "        \n",
    "        d = {}\n",
    "        rs = 0\n",
    "        left_idx = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in d:  # 见过，左边界取之前字符的下一个（如果下标比当前左边界大的话）\n",
    "                left_idx = max(d[ch]+1, left_idx)\n",
    "            rs = max(rs, i-left_idx+1)\n",
    "            d[ch] = i\n",
    "\n",
    "        \n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = 0, 0\n",
    "        map = dict()\n",
    "        res = 1\n",
    "        while right < n:\n",
    "            map[s[right]] = map.get(s[right], 0) + 1\n",
    "            while map[s[right]] == 2:\n",
    "                map[s[left]] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # if not s:\n",
    "        #     return 0\n",
    "        # res = 0\n",
    "        # left = 0\n",
    "        # sub = []\n",
    "        # for i in range(len(s)):\n",
    "        #     # 当新遍历到的值在sub数组中，就一直把最开始加入到sub\n",
    "        #     # 的值弹出，直到s[i]不在sub中\n",
    "        #     while s[i] in sub:\n",
    "        #         sub.pop(0)\n",
    "        #     sub.append(s[i])\n",
    "        #     # 每次遍历到一个值，因为上一步的弹出，总是保证sub数组里\n",
    "        #     # 的值不重复，所以每次动态保存最大的值\n",
    "        #     res = max(res, len(sub))\n",
    "        # return res\n",
    "\n",
    "        if not s:\n",
    "            return 0\n",
    "        res = 0\n",
    "        sub = []\n",
    "        for i in range(len(s)):\n",
    "            while s[i] in sub:\n",
    "                sub.pop(0)\n",
    "            sub.append(s[i])\n",
    "            res = max(res, len(sub))\n",
    "        return res\n",
    "       \n",
    "       \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/wo-xie-le--f02cd/\n",
    "class Solution:\n",
    "\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        window = {}  # 用于记录窗口中各字符出现的次数\n",
    "        left, right = 0, 0  # 窗口的左右边界\n",
    "        res = 0  # 用于记录结果\n",
    "\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            window[c] = window.get(c, 0) + 1  # 更新窗口和字符的出现次数\n",
    "\n",
    "            # 判断窗口是否需要收缩\n",
    "            while window[c] > 1:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                window[d] -= 1  # 更新窗口和字符的出现次数\n",
    "\n",
    "            res = max(res, right - left)  # 更新结果\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        start = maxLength = 0\n",
    "        usedChar = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in usedChar and start <= usedChar[s[i]]:\n",
    "                start = usedChar[s[i]] + 1\n",
    "            else:\n",
    "                maxLength = max(maxLength, i - start + 1)\n",
    "            usedChar[s[i]] = i\n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n <= 1: return n\n",
    "        max_len, window = 0, [0]*128\n",
    "        left = right = 0\n",
    "        while right < n:\n",
    "            right_char_index = window[ord(s[right])]\n",
    "            left = max(left, right_char_index)\n",
    "            max_len = max(max_len, right - left + 1)\n",
    "            window[ord(s[right])] = right + 1\n",
    "            right += 1\n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n=0\n",
    "        m=1\n",
    "        answer=''\n",
    "        while n+len(answer) <len(s):\n",
    "            substring=s[n:m]\n",
    "            if len(set(substring))==len(substring):\n",
    "                m=m+1\n",
    "                if len(substring) > len(answer):\n",
    "                    answer=substring\n",
    "            else:\n",
    "                n=n+1\n",
    "                m=n+len(answer)\n",
    "        return len(answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        max_length = 0  # 最大长度\n",
    "        left = 0  # 左指针\n",
    "\n",
    "        # 使用字典来存储字符的索引，用于快速查找重复字符的位置\n",
    "        char_index = {}\n",
    "\n",
    "        for right, c in enumerate(s):\n",
    "            # 如果字符在字典中，并且其索引大于等于左指针，则更新左指针位置\n",
    "            if c in char_index and char_index[c] >= left:\n",
    "                left = char_index[c] + 1\n",
    "\n",
    "            # 更新字符的索引\n",
    "            char_index[c] = right\n",
    "\n",
    "            # 更新最大长度\n",
    "            max_length = max(max_length, right - left + 1)\n",
    "\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # hashtable = defaultdict(int)\n",
    "        # length = len(s)\n",
    "        # left = 0\n",
    "        \n",
    "        # maxlen = 0\n",
    "        # for right in range(length):\n",
    "        #     hashtable[s[right]] += 1\n",
    "        #     while hashtable[s[right]] > 1:\n",
    "        #         hashtable[left] -= 1\n",
    "        #         left += 1\n",
    "        #     maxlen = max(maxlen, right - left + 1)\n",
    "        # return maxlen \n",
    "\n",
    "        left = 0\n",
    "        res = 0\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(s)\n",
    "        for right in range(n):\n",
    "            cnt[s[right]] += 1\n",
    "            while cnt[s[right]] > 1:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i, j = 0, 0\n",
    "        l = []\n",
    "        ans = 0\n",
    "        while j < n:\n",
    "            if s[j] in l:\n",
    "                ans = max(j - i, ans)\n",
    "            while s[j] in l:\n",
    "                l.pop(0)\n",
    "                i += 1\n",
    "            l.append(s[j])\n",
    "            j += 1\n",
    "        return max(ans,j - i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        chardict = {}\n",
    "        begin = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] in chardict):\n",
    "                begin = max(begin, chardict[s[i]] + 1)\n",
    "            res = max(res, i - begin + 1)\n",
    "            chardict[s[i]] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        current = []  # 当前的滑动窗口\n",
    "        res = 0  \n",
    "        for i in range(len(s)):\n",
    "            while s[i] in current:\n",
    "                current.pop(0)\n",
    "            current.append(s[i])\n",
    "            res = max(len(current),res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n= len(s)\n",
    "        b=set()\n",
    "        j=c=0\n",
    "        for i in range(n):\n",
    "            while j<n and s[j] not in b:\n",
    "                b.add(s[j])\n",
    "                j+=1\n",
    "            if j-i > c:\n",
    "                c=j-i\n",
    "            b.discard(s[i])\n",
    "        return c\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # 哈希 + 滑动窗口\n",
    "        res = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        start = 0\n",
    "        for i in range(len(s)):\n",
    "            dic[s[i]] += 1\n",
    "            if dic[s[i]] > 1:\n",
    "                while dic[s[start]] < 2:\n",
    "                    dic[s[start]] -= 1\n",
    "                    start += 1\n",
    "                dic[s[i]] -= 1\n",
    "                start += 1\n",
    "            res = max(res, i - start + 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        cal = {}\n",
    "        left = 0\n",
    "        ret = 0\n",
    "        for i,j in enumerate(s):\n",
    "            if j in cal:\n",
    "                left = max(left,cal[j]+1)\n",
    "            cal[j] = i\n",
    "            ret = max(ret,i-left+1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # hashtable = defaultdict(int)\n",
    "        # length = len(str)\n",
    "        # left = 0\n",
    "        \n",
    "        # maxlen = 0\n",
    "        # for right in range(n):\n",
    "        #     hashtable[]\n",
    "        occ = set()\n",
    "        n = len(s)\n",
    "        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动\n",
    "        rk, ans = -1, 0\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                # 左指针向右移动一格，移除一个字符\n",
    "                occ.remove(s[i - 1])\n",
    "            while rk + 1 < n and s[rk + 1] not in occ:\n",
    "                # 不断地移动右指针\n",
    "                occ.add(s[rk + 1])\n",
    "                rk += 1\n",
    "            # 第 i 到 rk 个字符是一个极长的无重复字符子串\n",
    "            ans = max(ans, rk - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        right = 0\n",
    "        left = 0\n",
    "        max_len = 0\n",
    "        s_dic = {}\n",
    "\n",
    "        for i,x in enumerate(s):\n",
    "            if x in s_dic and s_dic[x] >= left:\n",
    "                left = s_dic[x] +1\n",
    "\n",
    "            s_dic[x] = i\n",
    "            right = i\n",
    "\n",
    "            max_len = max(max_len,right-left+1)\n",
    "\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        right = 0\n",
    "        left = 0\n",
    "        s_dic = {}\n",
    "        max_len = 0\n",
    "\n",
    "        for i, x in enumerate(s):\n",
    "            if x in s_dic:\n",
    "                left = max(left, s_dic[x] + 1)\n",
    "            s_dic[x] = i\n",
    "            right = i\n",
    "         \n",
    "            max_len = max(max_len, right - left + 1)\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        occ = set() # 哈希集合，记录每个字符是否出现过\n",
    "        n = len(s)\n",
    "        rk, ans = -1, 0  # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                occ.remove(s[i - 1])  # 左指针向右移动一格，移除一个字符\n",
    "            while rk + 1 < n and s[rk + 1] not in occ:\n",
    "                occ.add(s[rk + 1])  # 不断地移动右指针\n",
    "                rk += 1\n",
    "            ans = max(ans, rk - i + 1) # 第 i 到 rk 个字符是一个极长的无重复字符子串\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        calc = dict()\n",
    "\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c in calc:\n",
    "                left = max(calc[c]+1, left)\n",
    "\n",
    "            calc[c] = i\n",
    "        \n",
    "            res = max(res, i - left + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        '''\n",
    "        f(i) := longest length of substring ended at s[i] without duplicated charaters\n",
    "        return max(f(1), f(2), ..., f(n))\n",
    "        f(i) = 1 for i in (1 to n) at the beginning\n",
    "        f(i+1) = f(i)+1 if s[i+1] not in s[i-f(i)+1, i] else 1\n",
    "        '''\n",
    "        # we can set a sliding window\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        sliding_window = set()\n",
    "        start, end = 0,1\n",
    "        sliding_window.add(s[start])\n",
    "        max_len = 0\n",
    "        while end < len(s):\n",
    "            if max_len < len(sliding_window):\n",
    "                max_len = len(sliding_window)\n",
    "            while s[end] in sliding_window:\n",
    "                sliding_window.discard(s[start])\n",
    "                start += 1\n",
    "            sliding_window.add(s[end])\n",
    "            end += 1\n",
    "\n",
    "        return max(max_len, len(sliding_window))           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if s=='':\n",
    "            return 0\n",
    "        else:\n",
    "            l = len(s)\n",
    "            i,j = 0,0\n",
    "            maxlen = 1\n",
    "            judge = set(s[0])\n",
    "            while j<l-1:\n",
    "                j+=1\n",
    "                if not s[j] in judge:\n",
    "                    judge.add(s[j])\n",
    "                    if j==l-1:\n",
    "                        if j-i+1>maxlen:\n",
    "                            maxlen = j-i+1\n",
    "                else:\n",
    "                    if j-i>maxlen:\n",
    "                        maxlen = j-i\n",
    "                    while s[i]!=s[j]:\n",
    "                        judge.remove(s[i])\n",
    "                        i+=1\n",
    "                    i+=1\n",
    "            \n",
    "            return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if s is None or len(s)==0:\n",
    "            return 0 \n",
    "        n = len(s)\n",
    "        lo = 0 \n",
    "        ans = 0\n",
    "        track = set()\n",
    "        for i in range(n):\n",
    "            if s[i] not in track:\n",
    "                track.add(s[i])\n",
    "                ans = max(ans, len(track))\n",
    "            else:\n",
    "                while lo<i and s[i] in track:\n",
    "                    track.remove(s[lo])\n",
    "                    lo += 1 \n",
    "                track.add(s[i])\n",
    "                \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = set()\n",
    "        ans = j = 0\n",
    "        for i in range(n):\n",
    "            while j < n and s[j] not in pre:\n",
    "                pre.add(s[j])\n",
    "                j += 1\n",
    "            if j - i > ans:\n",
    "                ans = j - i\n",
    "            pre.discard(s[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left , right = 0, 0\n",
    "        max_length = 0\n",
    "        exist = {}\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in exist and left <= exist[s[right]]:\n",
    "                left = exist[s[right]] + 1\n",
    "            else:\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "            exist[s[right]] = right\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        result = j = 0\n",
    "        for i in range(len(s)):\n",
    "            j = max(s[0:i].rfind(s[i]) + 1, j)\n",
    "            result = max(result, i - j + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # hashtable = defaultdict(int)\n",
    "        # length = len(str)\n",
    "        # left = 0\n",
    "        \n",
    "        # maxlen = 0\n",
    "        # for right in range(n):\n",
    "        #     hashtable[]\n",
    "        left = 0\n",
    "        res = 0\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(s)\n",
    "        for right in range(n):\n",
    "            cnt[s[right]] += 1\n",
    "            while cnt[s[right]] > 1:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        worddict = defaultdict(list)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        max_length = 0\n",
    "        while right < len(s):\n",
    "            ## \n",
    "            if s[right] in worddict and worddict[s[right]][0] != 0:\n",
    "                ## 重复字符 \n",
    "                dup_pos = worddict[s[right]][1]               \n",
    "                while left < dup_pos:\n",
    "                    worddict[s[left]] = [0,-1]\n",
    "                    left +=1 \n",
    "                worddict[s[left]][1] = right\n",
    "                left += 1\n",
    "            else:\n",
    "                worddict[s[right]] = [1,right]\n",
    "            if max_length < right - left +1:\n",
    "                max_length = right-left+ 1\n",
    "            right += 1\n",
    "        return max_length\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        res = 0\n",
    "        sub = []\n",
    "        for i in range(len(s)):\n",
    "            # 当新遍历到的值在sub数组中，就一直把最开始加入到sub\n",
    "            # 的值弹出，直到s[i]不在sub中\n",
    "            while s[i] in sub:\n",
    "                sub.pop(0)\n",
    "            sub.append(s[i])\n",
    "            # 每次遍历到一个值，因为上一步的弹出，总是保证sub数组里\n",
    "            # 的值不重复，所以每次动态保存最大的值\n",
    "            res = max(res, len(sub))\n",
    "        return res\n",
    "\n",
    "       \n",
    "       \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        \n",
    "        l, r = 0, 1\n",
    "        max_length = 0\n",
    "        dict = collections.Counter(s[l:r])\n",
    "\n",
    "        while l <= len(s) and r <= len(s):\n",
    "            dict = collections.Counter(s[l:r])\n",
    "            # print(l, r, dict)\n",
    "            if max(dict.values()) < 2:\n",
    "                max_length = max(max_length, r - l)\n",
    "                r += 1\n",
    "                # print(\"new r \", r)\n",
    "            else:\n",
    "                l += 1\n",
    "                # print(\"new l \", l)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        windows_set = set()\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for c in s:\n",
    "            while c in windows_set:\n",
    "                windows_set.remove(s[left])\n",
    "                left += 1\n",
    "            windows_set.add(c)\n",
    "            ans = max(ans, len(windows_set))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = 0\n",
    "        sub = []\n",
    "        for i in range(len(s)):\n",
    "            while s[i] in sub:\n",
    "                sub.pop(0)\n",
    "            sub.append(s[i])\n",
    "            res = max(res, len(sub))\n",
    "        return res\n",
    "       \n",
    "       \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        max_length = 0\n",
    "        map = dict()\n",
    "        # 字典用于存储 字符串:index\n",
    "        # 如果当前元素已经存在于字典key，即为不满足\n",
    "        # 左元素del，左节点+=1，\n",
    "\n",
    "        while l < len(s) and r < len(s):\n",
    "            element = s[r]\n",
    "            if element not in map.keys():\n",
    "                map[element] = r\n",
    "                max_length = max(max_length, r - l+1)\n",
    "                r += 1\n",
    "            else:\n",
    "                del map[s[l]]\n",
    "                l += 1\n",
    "                # print(\"new l \", l)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        calc = dict()\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c in calc:\n",
    "                left = max(left, calc[c]+1)\n",
    "            calc[c] = i\n",
    "            res =  max(res, i - left + 1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if len(s) <= 1:\n",
    "            return len(s)\n",
    "        a = 0\n",
    "        b = 0\n",
    "        cur_max = 1\n",
    "        tmp_set = set()\n",
    "        while a < len(s):\n",
    "            while b < len(s) and s[b] not in tmp_set:\n",
    "                tmp_set.add(s[b])\n",
    "                b += 1\n",
    "            cur_max = max(cur_max,b-a)\n",
    "            tmp_set.remove(s[a])\n",
    "            a += 1\n",
    "        return(cur_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        c2idx = {}\n",
    "        left_idx = 0\n",
    "        max_len = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c in c2idx:\n",
    "                old_idx = c2idx[c]\n",
    "                left_idx = max(old_idx + 1, left_idx)\n",
    "            c2idx[c] = i\n",
    "            tmp_len = i - left_idx + 1\n",
    "            max_len = max(tmp_len, max_len)\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        left,right = 0,0\n",
    "        cur = []\n",
    "        cur_dict = dict()\n",
    "        ans = -1\n",
    "        while right < len(s):\n",
    "            if s[right] not in cur_dict:\n",
    "                cur_dict[s[right]] = 1\n",
    "            else:\n",
    "                cur_dict[s[right]] += 1\n",
    "            while cur_dict[s[right]] > 1:\n",
    "                cur_dict[s[left]] -= 1\n",
    "                left += 1\n",
    "            ans = max(ans,right-left+1)\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        window={}\n",
    "        left,right=0,0\n",
    "        res=0\n",
    "        while right<len(s):\n",
    "            c=s[right]\n",
    "            right+=1\n",
    "            if c not in window:\n",
    "                window[c]=1\n",
    "            else:\n",
    "                window[c]+=1\n",
    "            while window[c]>1:\n",
    "                d=s[left]\n",
    "                left+=1\n",
    "                window[d]-=1\n",
    "            res=max(res,right-left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        lens = len(s)\n",
    "        l=0\n",
    "        has = set()\n",
    "        max_lens = 0\n",
    "        for r in range(lens):\n",
    "            if s[r] not in has:\n",
    "                has.add(s[r])\n",
    "                if r==lens-1:\n",
    "                    max_lens = max(max_lens,r-l+1)\n",
    "            else:\n",
    "                max_lens = max(max_lens,r-l)\n",
    "                while s[l]!=s[r]:\n",
    "                    has.remove(s[l])\n",
    "                    l+=1\n",
    "                l+=1\n",
    "                has.add(s[r])\n",
    "        return max_lens\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = 0\n",
    "        sub = []\n",
    "        for i in range(len(s)):\n",
    "            while s[i] in sub:\n",
    "                sub.pop(0)\n",
    "            sub.append(s[i])\n",
    "            res = max(res, len(sub))\n",
    "        return res\n",
    "       \n",
    "       \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n<=1:\n",
    "            return n\n",
    "        i=0\n",
    "        j=1\n",
    "        maxl = 0\n",
    "        while i<n and j<n:\n",
    "            print(i,j)\n",
    "            if s[j] not in set(s[i:j]):\n",
    "                j+=1\n",
    "            elif i<=j:\n",
    "                maxl = max(maxl,j-i)\n",
    "                i+=1\n",
    "            if j>=n:\n",
    "                maxl = max(maxl,j-i)\n",
    "        print(maxl)\n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        occ = set()\n",
    "        rk, ans = -1, 0\n",
    "        n = len(s)\n",
    "        for l in range(n):\n",
    "            if l != 0:\n",
    "                occ.remove(s[l-1])\n",
    "            while rk+1 < n and s[rk+1] not in occ:\n",
    "                occ.add(s[rk+1])\n",
    "                rk += 1\n",
    "            ans = max (ans, rk - l +1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        calc = {}\n",
    "        left = 0\n",
    "        ret = 0\n",
    "        for i, j in enumerate(s):\n",
    "            if j in calc:\n",
    "                # 如果重复的数字出现在l之前忽略，否则了跳到该值的下一个位置\n",
    "                left = max(left, calc[j] + 1)\n",
    "            calc[j] = i\n",
    "            ret = max(ret, i - left + 1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        dct = {}\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        if len(s) == 0 or len(s) == 1:\n",
    "            return len(s)\n",
    "        dct[s[r]] = 1\n",
    "        while r < len(s)-1:\n",
    "            r += 1\n",
    "            while s[r] in dct:\n",
    "                del dct[s[l]]\n",
    "                l += 1\n",
    "            dct[s[r]] = 1\n",
    "            res = max(res, r-l+1)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
